#ifndef _ALGORITHM_H_
#define _ALGORITHM_H_

#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>

namespace mystl {

template<typename InputIterator>
inline typename std::iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last) {
    return mystl::distance(first, last,
                           typename std::iterator_traits<InputIterator>::iterator_category());
}

template<typename RandomAccessIterator>
inline typename std::iterator_traits<RandomAccessIterator>::difference_type
distance(RandomAccessIterator first, RandomAccessIterator last, std::random_access_iterator_tag) {
    return last -first;
}

template<typename InputIterator>
inline typename std::iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last, std::input_iterator_tag) {
    typename std::iterator_traits<InputIterator>::difference_type n = 0;
    while (first != last) {
        ++first;
        ++n;
    }
    return n;
}

template <typename InputIterator, typename OutputIterator>
inline OutputIterator copy(InputIterator beg, InputIterator end, OutputIterator desBeg) {
    while (beg != end) {
        *desBeg++ = *beg++;
    }
    return desBeg;
}

template <typename InputIterator, typename T>
InputIterator find(InputIterator beg, InputIterator end, const T &value) {
    for (; beg != end && *beg != value; ++beg) {}
    return beg;
}

template <typename InputIterator, typename UnaryPredicate>
InputIterator find_if(InputIterator beg, InputIterator end, UnaryPredicate predicate) {
    for (; beg != end && !predicate(*beg); ++beg) {}
    return beg;
}

template <typename InputIterator, typename UnaryPredicate>
InputIterator find_if_not(InputIterator beg, InputIterator end, UnaryPredicate predicate) {
    for (; beg != end && predicate(*beg); ++beg) {}
    return beg;
}

template <typename ForwardIterator, typename Comp>
ForwardIterator min_element(ForwardIterator beg, ForwardIterator end, Comp comp) {
    if (beg == end) {
        return beg;
    }
    auto min = beg;
    while (++beg != end) {
        if (comp(*beg, *min)) {
            min = beg;
        }
    }
    return min;
}

template <typename ForwardIterator>
ForwardIterator min_element(ForwardIterator beg, ForwardIterator end) {
    return min_element(beg, end, std::less<decltype(*beg)>());
}

template <typename ForwardIterator, typename Comp>
ForwardIterator max_element(ForwardIterator beg, ForwardIterator end, Comp comp) {
    if (beg == end) {
        return beg;
    }
    auto max = beg;
    while (++beg != end) {
        if (comp(*max, *beg)) {
            max = beg;
        }
    }
    return max;
}

template <typename ForwardIterator>
ForwardIterator max_element(ForwardIterator beg, ForwardIterator end) {
    return max_element(beg, end, std::less<decltype(*beg)>());
}

template <typename ForwardIterator, typename Comp>
std::pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator beg, ForwardIterator end, Comp comp) {
    if (beg == end) {
        return {beg, beg};
    }
    auto min = beg, max = beg;
    while (++beg != end) {
        if (comp(*beg, *min)) {
            min = beg;
        }
        if (comp(*max, *beg)) {
            max = beg;
        }
    }
    return {min, max};
}

template<typename ForwardIterator>
std::pair<ForwardIterator, ForwardIterator>
minmax_element(ForwardIterator beg, ForwardIterator end) {
    return minmax_element(beg, end, std::less<decltype(*beg)>());
}

template <typename InputIterator1, typename InputIterator2>
bool equal(InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2) {
    while (beg1 != end1) {
        if (*beg1++ != *beg2++) {
            return false;
        }
    }
    return true;
}

template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
bool equal(InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, BinaryPredicate predicate) {
    while (beg1 != end1) {
        if (!predicate(*beg1++, *beg2++)) {
            return false;
        }
    }
    return true;
}

template <typename InputIterator, typename T>
auto count(InputIterator beg, InputIterator end, const T &value) -> decltype(beg - beg) {
    auto num = beg - beg;
    while (beg != end) {
        if (*beg++ == value) {
            ++num;
        }
    }
    return num;
}

template <typename InputIterator, typename UnaryPredicate>
auto count_if(InputIterator beg, InputIterator end, UnaryPredicate predicate) ->decltype(beg - beg) {
    auto num = beg - beg;
    while (beg != end) {
        if (predicate(*beg++)) {
            ++num;
        }
    }
    return num;
}

template<typename ForwardIterator1, typename ForwardIterator2>
bool is_permutation(ForwardIterator1 beg1, ForwardIterator1 end1, ForwardIterator2 beg2) {
    for (; beg1 != end1; ++beg1, ++beg2) {
        if (*beg1 != *beg2) {
            break;
        }
    }
    if (beg1 == end1) {
        return true;
    }

    auto end2 = beg2;
    std::advance(end2, std::distance(beg1, end1));
    for (auto scan = beg1; scan != end1; ++scan) {
        if (scan != mystl::find(beg1, scan, *scan)) {
            continue;
        }

        auto matches = mystl::count(beg2, end2, *scan);
        if (matches == 0 || mystl::count(scan, end1, *scan) != matches) {
            return false;
        }
    }
    return true;
}

template<typename ForwardIterator1, typename Forwarditerator2, typename BinaryPredicate>
bool is_permutation(ForwardIterator1 beg1, ForwardIterator1 end1, Forwarditerator2 beg2, BinaryPredicate predicate) {
    for (; beg1 != end1; ++beg1, ++beg2) {
        if (!bool(predicate(*beg1, *beg2))) {
            break;
        }
    }
    if (beg1 == end1) {
        return true;
    }

    auto end2 = beg2;
    std::advance(end2, std::distance(beg1, end1));
    for (auto scan = beg1; scan != end1; ++scan) {
        using std::placeholders::_1;
        if (scan != mystl::find(beg1, scan, std::bind(predicate, _1, *scan))) {
            continue;
        }

        auto matches = mystl::count(beg2, end2, std::bind(predicate, _1, *scan));
        if (matches == 0 || mystl::count(scan, end1, std::bind(predicate, _1, *scan))) {
            return false;
        }
    }
    return true;
}

template<typename InputIterator1, typename InputIterator2>
std::pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2) {
    for (; beg1 != end1; ++beg1, ++beg2) {
        if (*beg1 != *beg2) {
            break;
        }
    }
    return {beg1, beg2};
}

template<typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
std::pair<InputIterator1, InputIterator2>
mismatch(InputIterator1 beg1, InputIterator1 end1, InputIterator2 beg2, BinaryPredicate predicate) {
    for (; beg1 != end1; ++beg1, ++beg2) {
        if (!predicate(*beg1, *beg2)) {
            break;
        }
    }
    return {beg1, beg2};
}

template <typename ForwardIterator, typename T>
ForwardIterator remove(ForwardIterator beg, ForwardIterator end, const T &elem) {
    auto pos = mystl::find(beg, end, elem);
    if (pos == end) {
        return end;
    }
    auto newEnd = pos;
    for (++pos; pos != end; ++pos) {
        if (*pos != elem) {
            *newEnd++ = std::move(*pos);
        }
    }
    return newEnd;
}

template <typename ForwardIterator, typename UnaryPredicate>
ForwardIterator remove_if(ForwardIterator beg, ForwardIterator end, UnaryPredicate predicate) {
    auto pos = mystl::find_if(beg, end, predicate);
    if (pos == end) {
        return end;
    }
    auto newEnd = pos;
    for (++pos; pos != end; ++pos) {
        if (!predicate(*pos)) {
            *newEnd++ = std::move(*pos);
        }
    }
    return newEnd;
}

template <typename InputIterator, typename OutputIterator, typename T>
OutputIterator remove_copy(InputIterator srcBeg, InputIterator srcEnd, OutputIterator desBeg, const T &elem) {
    while (srcBeg != srcEnd) {
        auto copy = *srcBeg++;
        if (copy != elem) {
            *desBeg++ = copy;
        }
    }
    return desBeg;
}

template <typename InputIterator, typename OutputIterator, typename UnaryPredicate>
OutputIterator remove_copy_if(InputIterator srcBeg, InputIterator srcEnd, OutputIterator desBeg, UnaryPredicate predicate) {
    while (srcBeg != srcEnd) {
        auto copy = *srcBeg++;
        if (!predicate(copy)) {
            *desBeg++ = copy;
        }
    }
    return desBeg;
}

template <typename ForwardIterator, typename BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator beg, ForwardIterator end, BinaryPredicate predicate) {
    if (beg == end) {
        return end;
    }
    auto previous = beg;
    while (++beg != end) {
        if (predicate(*previous, *beg)) {
            return previous;
        }
        ++previous;
    }
    return end;
}

template <typename ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator beg, ForwardIterator end) {
    return adjacent_find(beg, end, std::equal_to<decltype(*beg)>{});
}

template <typename ForwardIterator, typename BinaryPredicate>
ForwardIterator unique(ForwardIterator beg, ForwardIterator end, BinaryPredicate predicate) {
    beg = mystl::adjacent_find(beg, end, predicate);
    if (beg == end) {
        return end;
    }

    auto newEnd = beg++;
    while (++beg != end) {
        if (!predicate(*newEnd, *beg)) {
            *(++newEnd) = std::move(*beg);
        }
    }
    return ++newEnd;
}

template <typename ForwardIterator>
ForwardIterator unique(ForwardIterator beg, ForwardIterator end) {
    return mystl::unique(beg, end, std::equal_to<decltype(*beg)>());
}

template <typename InputIterator, typename OutputIterator, typename BinaryPredicate>
OutputIterator unique_copy(InputIterator srcBeg, InputIterator srcEnd, OutputIterator desBeg, BinaryPredicate predicate) {
    if (srcBeg == srcEnd) {
        return desBeg;
    }
    auto lastOutputElem = *srcBeg++;
    *desBeg++ = lastOutputElem;
    while (srcBeg != srcEnd) {
        auto currentElem = *srcBeg++;
        if (!predicate(lastOutputElem, currentElem)) {
            *desBeg++ = currentElem;
            lastOutputElem = std::move(currentElem);
        }
    }
    return desBeg;
}

template <typename InputIterator, typename OutputIterator>
OutputIterator unique_copy(InputIterator srcBeg, InputIterator srcEnd, OutputIterator desBeg) {
    return mystl::unique_copy(srcBeg, srcEnd, desBeg, std::equal_to<decltype(*srcBeg)>{});
}

template <typename ForwardIterator1, typename ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 beg, ForwardIterator1 end,
                        ForwardIterator2 searchBeg, ForwardIterator2 searchEnd) {
    if (searchBeg == searchEnd) {
        return beg;
    }
    auto start = beg;
    while ((start = mystl::find(start, end, *searchBeg)) != end) {
        auto i = start;
        auto j = searchBeg;
        while (++j != searchEnd && ++i != end && *i == *j);
        if (j == searchEnd) {
            return start;
        }
        ++start;
    }
    return end;
}

template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 beg, ForwardIterator1 end,
                        ForwardIterator2 searchBeg, ForwardIterator2 searchEnd,
                        BinaryPredicate predicate) {
    using std::placeholders::_1;
    if (searchBeg == searchEnd) {
        return beg;
    }
    auto start = beg;
    while ((start = mystl::find(start, end, std::bind(predicate, _1, *searchBeg))) != end) {
        auto i = start;
        auto j = searchBeg;
        while (++j != searchEnd && ++i != end && predicate(*i, *j));
        if (j == searchEnd) {
            return start;
        }
        ++start;
    }
    return end;
}

template <typename InputIterator, typename ForwardIterator>
InputIterator find_first_of(InputIterator beg, InputIterator end, ForwardIterator searchBeg, ForwardIterator searchEnd) {
    for (; beg != end; ++beg) {
        for (auto iter = searchBeg; iter != searchEnd; ++iter) {
            if (*beg == *iter) {
                return beg;
            }
        }
    }
    return end;
}

template <typename InputIterator, typename ForwardIterator, typename BinaryPredicate>
InputIterator find_first_of(InputIterator beg, InputIterator end,
                            ForwardIterator searchBeg, ForwardIterator searchEnd,
                            BinaryPredicate predicate) {
    for (; beg != end; ++beg) {
        for (auto iter = searchBeg; iter != searchEnd; ++iter) {
            if (predicate(*beg, *iter)) {
                return beg;
            }
        }
    }
    return end;
}

template <typename ForwardIterator1, typename ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 beg, ForwardIterator1 end,
                          ForwardIterator2 searchBeg, ForwardIterator2 searchEnd) {
    auto pos = mystl::search(beg, end, searchBeg, searchEnd);
    if (pos == end) {
        return end;
    }
    auto nextPos = pos;
    while ((nextPos = mystl::search(nextPos, end, searchBeg, searchEnd)) != end) {
        pos = nextPos;
        ++nextPos;
    }
    return pos;
}

template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 beg, ForwardIterator1 end,
                          ForwardIterator2 searchBeg, ForwardIterator2 searchEnd,
                          BinaryPredicate predicate) {
    auto pos = mystl::search(beg, end, searchBeg, searchEnd, predicate);
    if (pos == end) {
        return end;
    }
    auto nextPos = pos;
    while ((nextPos = mystl::search(nextPos, end, searchBeg, searchEnd, predicate)) != end) {
        pos = nextPos;
        ++nextPos;
    }
    return pos;
}

template <typename ForwardIterator, typename T>
bool binary_search(ForwardIterator beg, ForwardIterator end, const T &elem) {
    if (beg == end) {
        return false;
    }
    auto size = std::distance(beg, end);
    auto middle = beg;
    std::advance(middle, size / 2);

    if (elem < *middle) {
        return mystl::binary_search(beg, middle, elem);
    } else if (*middle < elem) {
        return mystl::binary_search(++middle, end, elem);
    } else {
        return true;
    }
}

template <typename ForwardIterator, typename T, typename Comp>
bool binary_search(ForwardIterator beg, ForwardIterator end, const T &elem, Comp comp) {
    if (beg == end) {
        return false;
    }
    auto size = std::distance(beg, end);
    auto middle = beg;
    std::advance(middle, size / 2);

    if (comp(elem, *middle)) {
        return mystl::binary_search(beg, middle, elem, comp);
    } else if (comp(*middle, elem)) {
        return mystl::binary_search(++middle, end, elem, comp);
    } else {
        return true;
    }
}

template <typename InputIterator1, typename InputIterator2>
bool includes(InputIterator1 beg, InputIterator1 end, InputIterator2 searchBeg, InputIterator2 searchEnd) {
    if (searchBeg == searchEnd) {
        return true;
    }

    while ((beg = mystl::find(beg, end, *searchBeg)) != end) {
        if (++searchBeg == searchEnd) {
            return true;
        }
        ++beg;
    }
    return false;
}

template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>
bool includes(InputIterator1 beg, InputIterator1 end,
              InputIterator2 searchBeg, InputIterator2 searchEnd,
              BinaryPredicate predicate) {
    using std::placeholders::_1;
    if (searchBeg == searchEnd) {
        return true;
    }

    while ((beg = mystl::find_if(beg, end, std::bind(predicate, _1, *searchBeg))) != end) {
        if (++searchBeg == searchEnd) {
            return true;
        }
        ++beg;
    }
    return false;
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comp>
OutputIterator set_union(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                         InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                         OutputIterator desBeg, Comp comp) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (comp(*srcBeg1, *srcBeg2)) {
            *desBeg++ = *srcBeg1++;
        } else if (comp(*srcBeg2, *srcBeg1)) {
            *desBeg++ = *srcBeg2++;
        } else {
            *desBeg++ = *srcBeg1++;
            ++srcBeg2;
        }
    }
    if (srcBeg1 != srcEnd1) {
        return mystl::copy(srcBeg1, srcEnd1, desBeg);
    } else {
        return mystl::copy(srcBeg2, srcEnd2, desBeg);
    }
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_union(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                         InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                         OutputIterator desBeg) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (*srcBeg1 < *srcBeg2) {
            *desBeg++ = *srcBeg1++;
        } else if (*srcBeg2 < *srcBeg1) {
            *desBeg++ = *srcBeg2++;
        } else {
            *desBeg++ = *srcBeg1++;
            ++srcBeg2;
        }
    }
    if (srcBeg1 != srcEnd1) {
        return mystl::copy(srcBeg1, srcEnd1, desBeg);
    } else {
        return mystl::copy(srcBeg2, srcEnd2, desBeg);
    }
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comp>
OutputIterator set_difference(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                              InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                              OutputIterator desBeg, Comp comp) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (comp(*srcBeg1, *srcBeg2)) {
            *desBeg++ = *srcBeg1++;
        } else if (comp(*srcBeg2, *srcBeg1)) {
            ++srcBeg2;
        } else {
            ++srcBeg1;
            ++srcBeg2;
        }
    }
    return mystl::copy(srcBeg1, srcEnd1, desBeg);
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_difference(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                              InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                              OutputIterator desBeg) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (*srcBeg1 < *srcBeg2) {
            *desBeg++ = *srcBeg1++;
        } else if (*srcBeg2 < *srcBeg1) {
            ++srcBeg2;
        } else {
            ++srcBeg1;
            ++srcBeg2;
        }
    }
    return mystl::copy(srcBeg1, srcEnd1, desBeg);
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comp>
OutputIterator set_intersection(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                                InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                                OutputIterator desBeg, Comp comp) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (comp(*srcBeg1, *srcBeg2)) {
            ++srcBeg1;
        } else if (comp(*srcBeg2, *srcBeg1)) {
            ++srcBeg2;
        } else {
            *desBeg++ = *srcBeg1++;
            ++srcBeg2;
        }
    }
    return desBeg;
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_intersection(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                                InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                                OutputIterator desBeg) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (*srcBeg1 < *srcBeg2) {
            ++srcBeg1;
        } else if (*srcBeg2 < *srcBeg1) {
            ++srcBeg2;
        } else {
            *desBeg++ = *srcBeg1++;
            ++srcBeg2;
        }
    }
    return desBeg;
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Comp>
OutputIterator set_symmetric_difference(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                                        InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                                        OutputIterator desBeg, Comp comp) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (comp(*srcBeg1, *srcBeg2)) {
            *desBeg++ = *srcBeg1++;
        } else if (comp(*srcBeg2, *srcBeg1)) {
            *desBeg++ = *srcBeg2++;
        } else {
            ++srcBeg1;
            ++srcBeg2;
        }
    }
    if (srcBeg1 != srcEnd1) {
        return mystl::copy(srcBeg1, srcEnd1, desBeg);
    } else {
        return mystl::copy(srcBeg2, srcEnd2, desBeg);
    }
}

template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 srcBeg1, InputIterator1 srcEnd1,
                                        InputIterator2 srcBeg2, InputIterator2 srcEnd2,
                                        OutputIterator desBeg) {
    while (srcBeg1 != srcEnd1 && srcBeg2 != srcEnd2) {
        if (*srcBeg1 < *srcBeg2) {
            *desBeg++ = *srcBeg1++;
        } else if (*srcBeg2 > *srcBeg1) {
            *desBeg++ = *srcBeg2++;
        } else {
            ++srcBeg1;
            ++srcBeg2;
        }
    }
    if (srcBeg1 != srcEnd1) {
        return mystl::copy(srcBeg1, srcEnd1, desBeg);
    } else {
        return mystl::copy(srcBeg2, srcEnd2, desBeg);
    }
}

template <typename BidirectionalIterator>
void reverse(BidirectionalIterator beg, BidirectionalIterator end) {
    using std::swap;
    for (auto size = std::distance(beg, end); size >= 2; size -= 2) {
        swap(*beg++, *--end);
    }
}

template <typename BidirectionalIterator, typename OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator beg, BidirectionalIterator end, OutputIterator desBeg) {
    while (end != beg) {
        *desBeg++ = *--end;
    }
    return desBeg;
}

template <typename ForwardIterator, typename OutputIterator>
OutputIterator rotate_copy(ForwardIterator beg, ForwardIterator newBeg, ForwardIterator end, OutputIterator desBeg) {
    if (beg == end) {
        return desBeg;
    }
    auto current = newBeg;

    do {
        *desBeg++ = *current++;
        if (current == end) {
            current = beg;
        }
    } while (current != newBeg);
    return desBeg;
}

// TODO: what is this func for?
template <typename BidirectionalIterator, typename Comp>
bool next_permutation(BidirectionalIterator beg, BidirectionalIterator end, Comp comp) {
    using std::swap;
    if (beg == end) {
        return false;
    }
    auto current = beg;
    --current;
    while (current != beg) {
        auto next = current;
        --current;
        if (comp(*current, *next)) {
            auto iter = end;
            while (!comp(*current, *--iter));
            swap(*current, *iter);
            mystl::reverse(next, end);
            return true;
        }
    }
    return false;
}

template <typename BidirectionalIterator>
bool next_permutation( BidirectionalIterator beg, BidirectionalIterator end )
{
    return mystl::next_permutation( beg, end, std::less<decltype(*beg)>{} );
}

template <typename BidirectionalIterator, typename Comp>
bool prev_permutation( BidirectionalIterator beg, BidirectionalIterator end, Comp comp )
{
    using std::swap;
    if( beg == end )
    {
        return false;
    }
    auto current = beg;
    if( ++current == end )
    {
        return false;
    }
    current = end;
    --current;                       // current points to the last element
    while( current != beg )
    {
        auto next = current;
        --current;
        if( comp( *next, *current ) )
        {
            auto iter = end;
            while( !comp( *--iter, *current ) )
            {
            }
            swap( *current, *iter );
            mystl::reverse( next, end );
            return true;
        }
    }
    return false;
}

template <typename BidirectionalIterator>
bool prev_permutation( BidirectionalIterator beg, BidirectionalIterator end )
{
    return mystl::prev_permutation( beg, end, std::less<decltype(*beg)>{} );
}

template <typename RandomIterator>
void random_shuffle(RandomIterator beg, RandomIterator end) {
    if (beg == end) {
        return;
    }
    for (auto iter = beg + 1; iter != end; ++iter) {
        std::iter_swap(iter, beg + (std::rand() % ((iter - beg) + 1)));
    }
}

template <typename RandomIterator, typename RandomNumberGenerator>
void random_shuffle(RandomIterator beg, RandomIterator end, RandomNumberGenerator &&rand) {
    if (beg == end) {
        return;
    }
    for (auto iter = beg + 1; iter != end; ++iter) {
        std::iter_swap(iter, beg + rand((iter - beg) + 1));
    }
}

template <typename RandomIterator, typename UniformRandomNumberGenerator>
void shuffle(RandomIterator beg, RandomIterator end, UniformRandomNumberGenerator &&generator) {
    if (beg == end) {
        return;
    }
    std::uniform_int_distribution<unsigned> distribution;
    using range_type = decltype(distribution)::param_type;
    for (auto iter = beg + 1; iter != end; ++iter) {
        std::iter_swap(iter, beg + distribution(generator, range_type(0, iter - beg)));
    }
}

};      // namespace mystl

#endif  /* _ALGORITHM_H_ */